package sort;

import javafx.geometry.VPos;

import java.util.Arrays;

//快速排序，时间复杂度 O(nlogn)，80000个数据下 <1s。
public class QuickSort {
	public static void main(String[] args) {
		int[] array = {2, 1, 3};
		quickSort(array, 0, array.length - 1);
		System.out.println(Arrays.toString(array));
	}

	/**
	 * @param array:       数组
	 * @param right：右边的索引值
	 * @param left         ：左边的索引值
	 */
	public static void quickSort(int[] array, int left, int right) {
		int l = left;
		int r = right;
		int pivot = array[(left + right) / 2];
		int temp;//用于交换
		// 循环是为了让比 pivot 小的值放到左边，大的值放到右边
		while (l < r) {
			//在 中间值 的左边一直找大于等于 中间值 的值
			while (array[l] < pivot) {
				l += 1;
			}
			//在 中间值 的右边一直找小于等于 中间值 的值
			while (array[r] > pivot) {
				r -= 1;
			}
			//如果 l >= r 说明 pivot 左右两边的值已经按照左小右大拍好
			if (l >= r) {
				break;
			}

			//交换
			temp = array[l];
			array[l] = array[r];
			array[r] = temp;

			//因为上面已经完成交换所以肯定有 array[l] < array[r]
			//这时如果 array[l] = pivot，且这两个值靠在一起，就会出现死循环，所以需要已开一位让 l = r 退出循环
			//如果是 array[l] = pivot 时 l += 1，会出现把 array[l] 排除出了待排序的数组，容易出错


			//判断，交换完后，发现 array[l] == pivot 值，前移
			if (array[l] == pivot) {
				r -= 1;
			}
			//判断，交换完后，发现 array[r] == pivot 值，前移
			if (array[r] == pivot) {
				l += 1;
			}
		}

		//如果 l == r  必须让 l++, r--,否则栈溢出
		if (l == r) {
			l += 1;
			r -= 1;
		}
		if (left < r) {
			quickSort(array, left, r);
		}
		if (right > l) {
			quickSort(array, l, right);
		}
	}
}
